package october;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

/*
Implement an algorithm to print all possible valid combinations of braces when n pairs of paranthesis are given.
 */
public class ParenthesisGenerator {
    public static void main(String[] args) {
        int numberOfPairs = 4;
        System.out.println(printParenthesis(numberOfPairs));
        String bracketsToCheck = "((()(())))";
        System.out.println("Check the brackets: " + bracketsToCheck + ". Are they balanced?  --" + checkBalancedBrackets(bracketsToCheck));
        System.out.println("The next combination is " + getNextBalancedBrackets(bracketsToCheck));
        String lastBrackests = "((((((()))))))";
        System.out.println("Check the brackets: " + lastBrackests + ". Are they balanced?  --" + checkBalancedBrackets(lastBrackests));
        System.out.println("The next combination is " + getNextBalancedBrackets(lastBrackests));
    }

    private static Set<String> printParenthesis(int numberOfPairs) {
        if (numberOfPairs <= 0) throw new IllegalArgumentException("The number of pairs must be a positive number");
        if (numberOfPairs == 1) return Collections.singleton("()");
        Set<String> result = new HashSet<String>();
        for (String prevResult : printParenthesis(numberOfPairs - 1)) {
            result.add("(" + prevResult + ")");
            result.add("()" + prevResult);
            result.add(prevResult + "()");
        }
        return result;
    }

    private static Set<String> generateParenthesisNoRecursion(int numberOfPairs) {
        int numberOfLeftBrackets = 0;
        int numberOfRightBrackets = 0;
        Set<String> resultSet = new HashSet<String>();
        int i = 0;
        while (true) {
            if (numberOfLeftBrackets < numberOfPairs) {

            }
        }
    }

    private static boolean checkBalancedBrackets(String s) {
        if (s == null) return false;
        if (s.length() == 1) return false;
        int balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') balance++;
            else {
                if (c == ')') balance--;
                else return false;
            }
            if (balance < 0) return false;
        }
        return balance == 0;
    }

    private static String getNextBalancedBrackets(String s) {
        if (s == null | s.length() < 4) return "NO SOLUTION";
        char[] result = new char[s.length()];
        int i = s.length() - 1;
        int balance = 0;
        while (i >= 0) {
            final char c = s.toCharArray()[i];
            if (c == '(') {
                balance--;
                if (balance > 0) {
                    System.arraycopy(s.toCharArray(), 0, result, 0, i);
                    result[i++] = ')';
                    balance--;
                    int elementsLeft = s.length()-i;
                    int numberOfBracketsToOpen = (elementsLeft-balance)/2;
                    int numberOfBracketsToClose = (elementsLeft-numberOfBracketsToOpen);

                    for (int j = 0; j < numberOfBracketsToOpen; j++) {
                        result[i + j] = '(';
                    }
                    for (int j = 0; j < numberOfBracketsToClose; j++) {
                        result[i + numberOfBracketsToOpen + j] = ')';
                    }
                    return String.valueOf(result);
                }
            } else {
                if (c == ')') balance++;
                else return "NO SOLUTION";
            }
            i--;
        }
        return "NO SOLUTION";
    }
}

